home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / dynarray.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  19.9 KB  |  733 lines
  1. /*
  2.   File: Dynarray.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   2Oct95  dl@cs.oswego.edu   refactored from DASeq.java
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16. import java.util.Enumeration;
  17. import java.util.NoSuchElementException;
  18.  
  19. /**
  20.  *
  21.  * Dynamically allocated and resized Arrays.
  22.  * 
  23.  * Beyond implementing its interfaces, adds methods
  24.  * to adjust capacities. The default heuristics for resizing
  25.  * usually work fine, but you can adjust them manually when
  26.  * you need to.
  27.  *
  28.  * Dynarrays are generally like java.util.Vectors. But unlike them,
  29.  * Dynarrays do not actually allocate arrays when they are constructed.
  30.  * Among other consequences, you can adjust the capacity `for free'
  31.  * after construction but before adding elements. You can adjust
  32.  * it at other times as well, but this may lead to more expensive
  33.  * resizing. Also, unlike Vectors, they release their internal arrays
  34.  * whenever they are empty.
  35.  *
  36.  * @author Doug Lea
  37.  * @version 0.93
  38.  *
  39.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  40.  *
  41. **/
  42.  
  43. public class Dynarray extends    UpdatableSeqImpl 
  44.                       implements UpdatableSeq,
  45.                                  SortableCollection {
  46. /**
  47.  * The minimum capacity of any non-empty buffer
  48. **/
  49.  
  50.   public static final int minCapacity = 16;
  51.  
  52.  
  53. // instance variables
  54.  
  55. /**
  56.  * The elements, or null if no buffer yet allocated.
  57. **/
  58.  
  59.   protected Object array_[];
  60.  
  61.  
  62. // constructors
  63.  
  64. /**
  65.  * Make a new empty Dynarray. 
  66. **/
  67.  
  68.   public Dynarray() { this(null, null, 0); }
  69.  
  70. /**
  71.  * Make an empty Dynarray with given element screener
  72. **/
  73.  
  74.   public Dynarray(Predicate screener) { this(null, null, 0); }
  75.  
  76. /**
  77.  * Special version of constructor needed by clone()
  78. **/
  79.   protected Dynarray(Predicate s, Object b[], int c) { 
  80.     super(s); array_ = b; count_ = c;  
  81.   }
  82.  
  83. /**
  84.  * Make an independent copy. The elements themselves are not cloned
  85. **/
  86.  
  87.   protected Object clone() throws CloneNotSupportedException { 
  88.     int cap = count_;
  89.     if (cap == 0) 
  90.       return new Dynarray(screener_, null, 0);
  91.     else {
  92.       if (cap < minCapacity) cap = minCapacity;
  93.       Object newArray[] = new Object[cap];
  94.       System.arraycopy(array_, 0, newArray, 0, count_);
  95.       return new Dynarray(screener_, newArray, count_);
  96.     }
  97.   }
  98.  
  99. // methods introduced in Dynarray
  100.  
  101. /**
  102.  * return the current internal buffer capacity (zero if no buffer allocated).
  103.  * @return capacity (always greater than or equal to size())
  104. **/
  105.  
  106.   public synchronized int capacity() { 
  107.     return (array_ == null)? 0 : array_.length; 
  108.   }
  109.  
  110. /**
  111.  * Set the internal buffer capacity to max(size(), newCap).
  112.  * That is, if given an argument less than the current
  113.  * number of elements, the capacity is just set to the
  114.  * current number of elements. Thus, elements are never lost
  115.  * by setting the capacity. 
  116.  * 
  117.  * @param newCap the desired capacity.
  118.  * @return condition: 
  119.  * <PRE>
  120.  * capacity() >= size() &&
  121.  * version() != PREV(this).version() == (capacity() != PREV(this).capacity())
  122.  * </PRE>
  123. **/
  124.  
  125.   public synchronized void capacity(int newCap) {
  126.     if (newCap < count_) newCap = count_;
  127.     if (newCap == 0) {
  128.       clear();
  129.     }
  130.     else if (array_ == null) {
  131.       array_ = new Object[newCap];
  132.       incVersion();
  133.     }
  134.     else if (newCap != array_.length) {
  135.       Object newArray[] = new Object[newCap];
  136.       System.arraycopy(array_, 0, newArray, 0, count_);
  137.       array_ = newArray;
  138.       incVersion();
  139.     }
  140.   }
  141.  
  142.  
  143. // Collection methods
  144.  
  145. /**
  146.  * Implements collections.Collection.includes.
  147.  * Time complexity: O(n).
  148.  * @see collections.Collection#includes
  149. **/
  150.   public synchronized boolean includes(Object element) {
  151.     if (element == null) return false;
  152.     for (int i = 0; i < count_; ++i) 
  153.       if (array_[i].equals(element))
  154.         return true;
  155.     return false;
  156.   }
  157.  
  158. /**
  159.  * Implements collections.Collection.occurrencesOf.
  160.  * Time complexity: O(n).
  161.  * @see collections.Collection#occurrencesOf
  162. **/
  163.   public synchronized int occurrencesOf(Object element) {
  164.     if (element == null) return 0;
  165.     int c = 0;
  166.     for (int i = 0; i < count_; ++i) 
  167.       if (array_[i].equals(element)) ++c;
  168.     return c;
  169.   }
  170.  
  171. /**
  172.  * Implements collections.Collection.elements.
  173.  * Time complexity: O(1).
  174.  * @see collections.Collection#elements
  175. **/
  176.   public synchronized CollectionEnumeration elements() { 
  177.     return new DAEnumeration(this, array_); 
  178.   }
  179.  
  180.  
  181.  
  182. // Seq methods:
  183.  
  184. /**
  185.  * Implements collections.Seq.first.
  186.  * Time complexity: O(1).
  187.  * @see collections.Seq#first
  188. **/
  189.   public synchronized Object first()
  190.   throws  NoSuchElementException {
  191.     checkIndex(0);
  192.     return array_[0];
  193.   }
  194.  
  195. /**
  196.  * Implements collections.Seq.last.
  197.  * Time complexity: O(1).
  198.  * @see collections.Seq#last
  199. **/
  200.   public synchronized Object last()
  201.   throws  NoSuchElementException {
  202.     checkIndex(count_-1);
  203.     return array_[count_-1];
  204.   }
  205.  
  206. /**
  207.  * Implements collections.Seq.at.
  208.  * Time complexity: O(1).
  209.  * @see collections.Seq#at
  210. **/
  211.   public synchronized Object at(int index) 
  212.   throws  NoSuchElementException {
  213.     checkIndex(index);  
  214.     return array_[index]; 
  215.   }
  216.  
  217. /**
  218.  * Implements collections.Seq.firstIndexOf.
  219.  * Time complexity: O(n).
  220.  * @see collections.Seq#firstIndexOf
  221. **/
  222.   public synchronized int firstIndexOf(Object element, int startingIndex) {
  223.     if (startingIndex < 0) startingIndex = 0;
  224.     for (int i = startingIndex; i < count_; ++i) 
  225.       if (array_[i].equals(element))
  226.         return i;
  227.     return -1;
  228.   }
  229.  
  230. /**
  231.  * Implements collections.Seq.lastIndexOf.
  232.  * Time complexity: O(n).
  233.  * @see collections.Seq#lastIndexOf
  234. **/
  235.   public synchronized int lastIndexOf(Object element, int startingIndex) {
  236.     if (startingIndex >= count_) startingIndex = count_ -1;
  237.     for (int i = startingIndex; i >= 0; --i) 
  238.       if (array_[i].equals(element))
  239.         return i;
  240.     return -1;
  241.   }
  242.  
  243. /**
  244.  * Implements collections.Seq.firstIndexOf.
  245.  * Time complexity: O(n).
  246.  * @see collections.Seq#firstIndexOf
  247. **/
  248.   public synchronized int firstIndexOf(Object element) {
  249.     return firstIndexOf(element, 0);
  250.   }
  251.  
  252. /**
  253.  * Implements collections.Seq.lastIndexOf.
  254.  * Time complexity: O(n).
  255.  * @see collections.Seq#lastIndexOf
  256. **/
  257.   public synchronized int lastIndexOf(Object element) {
  258.     return lastIndexOf(element, size()-1);
  259.   }
  260.  
  261.  
  262. /**
  263.  * Implements collections.Seq.subseq.
  264.  * Time complexity: O(length).
  265.  * @see collections.Seq#subseq
  266. **/
  267.   public synchronized /* Dynarray */ Seq subseq(int from, int length) 
  268.   throws  NoSuchElementException {
  269.     if (length > 0) {
  270.       checkIndex(from);
  271.       checkIndex(from+length-1);
  272.       Object newArray[] = new Object[length];
  273.       System.arraycopy(array_, from, newArray, 0, length);
  274.       return new Dynarray(screener_, newArray, length);
  275.     }
  276.     else
  277.       return new Dynarray(screener_);
  278.   }
  279.  
  280.  
  281. // UpdatableCollection methods
  282.  
  283. /**
  284.  * Implements collections.UpdatableCollection.clear.
  285.  * Time complexity: O(1).
  286.  * @see collections.UpdatableCollection#clear
  287. **/
  288.   public synchronized void clear() { 
  289.     array_ = null;
  290.     setCount(0);
  291.   }
  292.  
  293. /**
  294.  * Implements collections.UpdatableCollection.removeOneOf.
  295.  * Time complexity: O(n).
  296.  * @see collections.UpdatableCollection#removeOneOf
  297. **/
  298.   public synchronized void removeOneOf(Object element)  { 
  299.     remove_(element, false);
  300.   }
  301.  
  302.  
  303. /**
  304.  * Implements collections.UpdatableCollection.replaceOneOf
  305.  * Time complexity: O(n).
  306.  * @see collections.UpdatableCollection#replaceOneOf
  307. **/
  308.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  
  309.   throws IllegalElementException { 
  310.     replace_(oldElement, newElement, false);
  311.   }
  312.  
  313. /**
  314.  * Implements collections.UpdatableCollection.replaceAllOf.
  315.  * Time complexity: O(n * number of replacements).
  316.  * @see collections.UpdatableCollection#replaceAllOf
  317. **/
  318.   public synchronized void replaceAllOf(Object oldElement, 
  319.                                                  Object newElement)  
  320.   throws IllegalElementException { 
  321.     replace_(oldElement, newElement, true);
  322.   }
  323.  
  324. /**
  325.  * Implements collections.UpdatableCollection.exclude.
  326.  * Time complexity: O(n * occurrencesOf(element)).
  327.  * @see collections.UpdatableCollection#exclude
  328. **/
  329.   public synchronized void exclude(Object element)  { 
  330.     remove_(element, true);
  331.   }
  332.  
  333. /**
  334.  * Implements collections.UpdatableCollection.take.
  335.  * Time complexity: O(1).
  336.  * Takes the rightmost element of the array.
  337.  * @see collections.UpdatableCollection#take
  338. **/
  339.   public synchronized Object take() 
  340.   throws  NoSuchElementException {
  341.     Object v = last();
  342.     removeLast();
  343.     return v;
  344.   }
  345.  
  346.  
  347. // SortableCollection methods:
  348.  
  349.  
  350. /**
  351.  * Implements collections.SortableCollection.sort.
  352.  * Time complexity: O(n log n).
  353.  * Uses a quicksort-based algorithm.
  354.  * @see collections.SortableCollection#sort
  355. **/
  356.   public void sort(Comparator cmp) {
  357.     if (count_ > 0) {
  358.       quickSort(array_, 0, count_ - 1, cmp);
  359.       incVersion();
  360.     }
  361.   }
  362.  
  363.  
  364. // UpdatableSeq methods     
  365.  
  366. /**
  367.  * Implements collections.UpdatableSeq.insertFirst.
  368.  * Time complexity: O(n)
  369.  * @see collections.UpdatableSeq#insertFirst
  370. **/
  371.   public synchronized void insertFirst(Object element) 
  372.   throws IllegalElementException {
  373.     checkElement(element);
  374.     growBy_(1);
  375.     for (int i = count_-1; i > 0; --i) array_[i] = array_[i-1];
  376.     array_[0] = element;
  377.   }
  378.  
  379. /**
  380.  * Implements collections.UpdatableSeq.replaceFirst.
  381.  * Time complexity: O(1).
  382.  * @see collections.UpdatableSeq#replaceFirst
  383. **/
  384.   public synchronized void replaceFirst(Object element) 
  385.   throws IllegalElementException {
  386.     checkElement(element);
  387.     array_[0] = element;
  388.     incVersion();
  389.   }
  390.  
  391. /**
  392.  * Implements collections.UpdatableSeq.removeFirst.
  393.  * Time complexity: O(n).
  394.  * @see collections.UpdatableSeq#removeFirst
  395. **/
  396.   public synchronized void removeFirst()
  397.   throws NoSuchElementException {
  398.     removeAt(0);
  399.   }
  400.  
  401. /**
  402.  * Implements collections.UpdatableSeq.insertLast.
  403.  * Time complexity: normally O(1), but O(n) if size() == capacity().
  404.  * @see collections.UpdatableSeq#insertLast
  405. **/
  406.   public synchronized void insertLast(Object element) 
  407.   throws IllegalElementException {
  408.     checkElement(element);
  409.     int last = count_;
  410.     growBy_(1);
  411.     array_[last] = element;
  412.   }
  413.  
  414. /**
  415.  * Implements collections.UpdatableSeq.replaceLast.
  416.  * Time complexity: O(1).
  417.  * @see collections.UpdatableSeq#replaceLast
  418. **/
  419.   public synchronized void replaceLast(Object element) 
  420.   throws IllegalElementException, NoSuchElementException {
  421.     checkElement(element);
  422.     array_[count_-1] = element;
  423.     incVersion();
  424.   }
  425.  
  426. /**
  427.  * Implements collections.UpdatableSeq.removeLast.
  428.  * Time complexity: O(1).
  429.  * @see collections.UpdatableSeq#removeLast
  430. **/
  431.   public synchronized void removeLast()
  432.   throws NoSuchElementException {
  433.     checkIndex(0);
  434.     array_[count_-1] = null;
  435.     growBy_(-1);
  436.   }
  437.  
  438. /**
  439.  * Implements collections.UpdatableSeq.insertAt.
  440.  * Time complexity: O(n).
  441.  * @see collections.UpdatableSeq#insertAt
  442. **/
  443.   public synchronized void insertAt(int index, Object element) 
  444.   throws IllegalElementException, NoSuchElementException {
  445.     if (index != count_) checkIndex(index);
  446.     checkElement(element);
  447.     growBy_(1);
  448.     for (int i = count_-1; i > index; --i) array_[i] = array_[i-1];
  449.     array_[index] = element;
  450.   }
  451.  
  452. /**
  453.  * Implements collections.UpdatableSeq.removeAt.
  454.  * Time complexity: O(n).
  455.  * @see collections.UpdatableSeq#removeAt
  456. **/
  457.   public synchronized void removeAt(int index) 
  458.   throws NoSuchElementException {
  459.     checkIndex(index);
  460.     for (int i = index+1; i < count_; ++i) array_[i-1] = array_[i];
  461.     array_[count_-1] = null;
  462.     growBy_(-1);
  463.   }
  464.     
  465.  
  466. /**
  467.  * Implements collections.UpdatableSeq.replaceAt.
  468.  * Time complexity: O(1).
  469.  * @see collections.UpdatableSeq#replaceAt
  470. **/
  471.   public synchronized void replaceAt(int index, Object element) 
  472.   throws IllegalElementException, NoSuchElementException {
  473.     checkIndex(index);
  474.     checkElement(element);
  475.     array_[index] = element;
  476.     incVersion();
  477.   }
  478.  
  479. /**
  480.  * Implements collections.UpdatableSeq.prependElements.
  481.  * Time complexity: O(n + number of elements in e) if (e 
  482.  * instanceof CollectionEnumeration) else O(n * number of elements in e)
  483.  * @see collections.UpdatableSeq#prependElements
  484. **/
  485.   public synchronized void prependElements(Enumeration e) 
  486.   throws IllegalElementException, CorruptedEnumerationException {
  487.     insertElementsAt_(0, e);
  488.   }
  489.  
  490. /**
  491.  * Implements collections.UpdatableSeq.appendElements.
  492.  * Time complexity: O(number of elements in e) 
  493.  * @see collections.UpdatableSeq#appendElements
  494. **/
  495.   public synchronized void appendElements(Enumeration e) 
  496.   throws IllegalElementException, CorruptedEnumerationException {
  497.     insertElementsAt_(count_, e);
  498.   }
  499.  
  500. /**
  501.  * Implements collections.UpdatableSeq.insertElementsAt.
  502.  * Time complexity: O(n + number of elements in e) if (e 
  503.  * instanceof CollectionEnumeration) else O(n * number of elements in e)
  504.  * @see collections.UpdatableSeq#insertElementsAt
  505. **/
  506.   public synchronized void insertElementsAt(int index, Enumeration e) 
  507.   throws IllegalElementException, CorruptedEnumerationException,
  508.   NoSuchElementException {
  509.     if (index != count_) checkIndex(index);
  510.     insertElementsAt_(index, e);
  511.   }
  512.  
  513.  
  514. /**
  515.  * Implements collections.UpdatableSeq.removeFromTo.
  516.  * Time complexity: O(n).
  517.  * @see collections.UpdatableSeq#removeFromTo
  518. **/
  519.   public synchronized void removeFromTo(int fromIndex, int toIndex) 
  520.   throws NoSuchElementException {
  521.     checkIndex(fromIndex);
  522.     checkIndex(toIndex);
  523.     if (fromIndex <= toIndex) {
  524.       int gap = toIndex - fromIndex + 1;
  525.       int j = fromIndex;
  526.       for (int i = toIndex+1; i < count_; ++i) array_[j++] = array_[i];
  527.       for (int i = 1; i <= gap; ++i) array_[count_-i] = null;
  528.       addToCount(-gap);
  529.     }
  530.   }
  531.  
  532. /**
  533.  * An implementation of Quicksort using medians of 3 for partitions.
  534.  * Used internally by sort.
  535.  * It is public and static so it can be used  to sort plain
  536.  * arrays as well.
  537.  * @param s, the array to sort
  538.  * @param lo, the least index to sort from
  539.  * @param hi, the greatest index
  540.  * @param cmp, the comparator to use for comparing elements
  541. **/
  542.  
  543.   public static void quickSort(Object s[], int lo, int hi, Comparator cmp) {
  544.  
  545.     if (lo >= hi) return;
  546.  
  547.     /* 
  548.        Use median-of-three(lo, mid, hi) to pick a partition. 
  549.        Also swap them into relative order while we are at it.
  550.    */
  551.   
  552.     int mid = (lo + hi) / 2;
  553.   
  554.     if (cmp.compare(s[lo], s[mid]) > 0) {
  555.       Object tmp = s[lo]; s[lo] = s[mid]; s[mid] = tmp; // swap
  556.     }
  557.     
  558.     if (cmp.compare(s[mid], s[hi]) > 0) {
  559.       Object tmp = s[mid]; s[mid] = s[hi]; s[hi] = tmp; // swap 
  560.       
  561.       if (cmp.compare(s[lo], s[mid]) > 0) {
  562.         Object tmp2 = s[lo]; s[lo] = s[mid]; s[mid] = tmp2; // swap
  563.       }
  564.       
  565.     }
  566.     
  567.     int left = lo+1;           // start one past lo since already handled lo
  568.     int right = hi-1;          // similarly
  569.     if (left >= right) return; // if three or fewer we are done
  570.     
  571.     Object partition = s[mid];
  572.     
  573.     for (;;) {
  574.       
  575.       while (cmp.compare(s[right], partition) > 0) --right;
  576.       
  577.       while (left < right && cmp.compare(s[left], partition) <= 0) ++left;
  578.       
  579.       if (left < right) {
  580.         Object tmp = s[left]; s[left] = s[right]; s[right] = tmp; // swap
  581.         --right;
  582.       }
  583.       else break;
  584.     }
  585.     
  586.     quickSort(s, lo, left, cmp);
  587.     quickSort(s, left+1, hi, cmp);
  588.     
  589.   }
  590.  
  591. // helper methods
  592.  
  593. /**
  594.  * Main method to control buffer sizing.
  595.  * The heuristic used for growth is:
  596.  * <PRE>
  597.  * if out of space:
  598.  *   if need less than minCapacity, grow to minCapacity
  599.  *   else grow by average of requested size and minCapacity.
  600.  * </PRE>
  601.  * <P>
  602.  * For small buffers, this causes them to be about 1/2 full.
  603.  * while for large buffers, it causes them to be about 2/3 full.
  604.  * <P>
  605.  * For shrinkage, the only thing we do is unlink the buffer if it is empty.
  606.  * @param inc, the amount of space to grow by. Negative values mean shrink.
  607.  * @return condition: adjust record of count, and if any of
  608.  * the above conditions apply, allocate and copy into a new
  609.  * buffer of the appropriate size.
  610. **/
  611.  
  612.   private void growBy_(int inc) {
  613.     int needed = count_ + inc;
  614.     if (inc > 0) {
  615.       /* heuristic: 
  616.      */
  617.       int current = capacity();
  618.       if (needed > current) {
  619.         incVersion();
  620.         int newCap = needed + (needed + minCapacity) / 2;
  621.         if (newCap < minCapacity) newCap = minCapacity;
  622.         if (array_ == null) {
  623.           array_ = new Object[newCap];
  624.         }
  625.         else {
  626.           Object newArray[] = new Object[newCap];
  627.           System.arraycopy(array_, 0, newArray, 0, count_);
  628.           array_ = newArray;
  629.         }
  630.       }
  631.     }
  632.     else if (needed == 0) 
  633.       array_ = null;
  634.     setCount(needed);
  635.   }
  636.  
  637.  
  638.   
  639.  
  640. /**
  641.  * Utility to splice in enumerations
  642. **/
  643.  
  644.   private void insertElementsAt_(int index, Enumeration e) 
  645.   throws CorruptedEnumerationException, IllegalElementException {
  646.     if (e instanceof CollectionEnumeration) { // we know size!
  647.       int inc = ((CollectionEnumeration)(e)).numberOfRemainingElements();
  648.       int oldcount = count_;
  649.       int oldversion = version_;
  650.       growBy_(inc); 
  651.       for (int i = oldcount-1; i >= index; --i) array_[i+inc] = array_[i];
  652.       int j = index;
  653.       while (e.hasMoreElements()) {
  654.         Object element = e.nextElement();
  655.         if (!canInclude(element)) { // Ugh. Can only do full rollback
  656.           for (int i = index; i < oldcount; ++i) array_[i] = array_[i+inc];
  657.           version_ = oldversion;
  658.           count_ = oldcount;
  659.           checkElement(element); // force throw
  660.         }
  661.         array_[j++] = element;
  662.       }
  663.     }
  664.     else if (index == count_) { // next best; we can append 
  665.       while (e.hasMoreElements()) {
  666.         Object element = e.nextElement();
  667.         checkElement(element);
  668.         growBy_(1);
  669.         array_[count_-1] = element;
  670.       }
  671.     }
  672.     else { // do it the slow way
  673.       int j = index;
  674.       while (e.hasMoreElements()) {
  675.         Object element = e.nextElement();
  676.         checkElement(element);
  677.         growBy_(1);
  678.         for (int i = count_-1; i > j; --i) array_[i] = array_[i-1];
  679.         array_[j++] = element;
  680.       }
  681.     }
  682.   }
  683.  
  684.   private void remove_(Object element, boolean allOccurrences)  {
  685.     if (element == null) return;
  686.     for (int i = 0; i < count_; ++i) {
  687.       while (i < count_ && array_[i].equals(element)) {
  688.         for (int j = i+1; j < count_; ++j) array_[j-1] = array_[j];
  689.         array_[count_-1] = null;
  690.         growBy_(-1);
  691.         if (!allOccurrences || count_ == 0) return;
  692.       }
  693.     }
  694.   }
  695.  
  696.   private void replace_(Object oldElement, Object newElement, boolean allOccurrences)  
  697.   throws IllegalElementException { 
  698.     if (oldElement == null || count_ == 0) return;
  699.     for (int i = 0; i < count_; ++i) {
  700.       if (array_[i].equals(oldElement)) {
  701.         checkElement(newElement);
  702.         array_[i] = newElement;
  703.         incVersion();
  704.         if (!allOccurrences) return;
  705.       }
  706.     }
  707.   }
  708.  
  709. // ImplementationCheckable methods
  710.  
  711. /**
  712.  * Implements collections.ImplementationCheckable.checkImplementation.
  713.  * @see collections.ImplementationCheckable#checkImplementation
  714. **/
  715.   public synchronized void checkImplementation() 
  716.   throws ImplementationError {
  717.  
  718.     super.checkImplementation();
  719.     assert(!(array_ == null && count_ != 0));
  720.     assert((array_ == null || count_ <= array_.length));
  721.  
  722.     for (int i = 0; i < count_; ++i) {
  723.       assert(canInclude(array_[i]));
  724.       assert(occurrencesOf(array_[i]) > 0);
  725.       assert(includes(array_[i]));
  726.     }
  727.  
  728.   }
  729.  
  730.  
  731. }
  732.  
  733.